public class unConvo {

  public static int[][] convoUnapply(int[] a) {
    return new int[][] {
                  jacobiIteration(Convo.convo(a.length), a, 5000000).fst,
                  gaussSeidelIteration(Convo.convo(a.length), a, 5000000).fst};
  }

  public static int[] stringToTwoBitIntArray(String a) {
    int[] is = new int[a.length()/2];
    for (int i = 0; i < is.length; i++) {
      int k = i * 2;
      String s = a.substring(k, k+2);
      if (s.equals("00"))
        is[i] = 0;
      else if (s.equals("01"))
        is[i] = 1;
      else if (s.equals("10"))
        is[i] = 2;
      else if (s.equals("11"))
        is[i] = 3;
      else
        throw new IllegalArgumentException("invalid bit string: " + a);
    }
    return is;
  }

  public static Tuple<int[][],int[][]> splitUpperLower(int[][] a) {
    int [][] l = new int[a.length][a.length == 0 ? 0 : a[0].length];
    int [][] u = new int[a.length][a.length == 0 ? 0 : a[0].length];
    for (int i = 0; i < a.length; i++)
      for (int j = 0; j < a[i].length; j++)
        (i < j ? u : l)[i][j] = a[i][j];
    return new Tuple<int[][],int[][]>(l, u);
  }

  public static Tuple<int[],Integer> gaussSeidelIteration(int[][] a, int [] b, int maxIterations) {
    Tuple<int[][],int[][]> lu = splitUpperLower(a);
    int [] x = new int[b.length];
    int [] ox = new int[b.length];
    for (int i = 0; i < x.length; i++)
      x[i] = Math.random() > .5 ? 1 : 0;
    int iterations = 0;
    while (iterations++ < maxIterations) {
      int diff = 0;
      for (int i = 0; i < x.length; i++)
        diff += Math.abs(x[i] - ox[i]);
      if (diff == 0)
        break;
      ox = x;
      x = Convo.apply(lu.snd, x);
      for (int i = 0; i < x.length; i++)
        x[i] = b[i] ^ x[i];
      x = forwardSubstitute(lu.fst, x);
    }
    return new Tuple<int[],Integer>(x, iterations);
  }

  public static int [] forwardSubstitute(int [][] matrix, int [] vector) {
    // Matrix is assumed to be in lower-triangular form
    if (matrix.length != vector.length)
      throw new IllegalArgumentException("solution has wrong dimension");
    int [] v = new int[vector.length];
    System.arraycopy(vector, 0, v, 0, v.length);
    int [] result = new int[matrix.length];
    for (int i = 0; i < result.length; i++) {
      result[i] = v[i] / matrix[i][i];
      for (int j = i; j < result.length; j++)
        v[j] ^= result[i] * matrix[j][i];
    }
    return result;
  }

  public static String oneBitIntArrayToString(int[] a) {
    StringBuilder sb = new StringBuilder();
    for (int i : a)
      if (i == 0)
        sb.append("0");
      else if (i == 1)
        sb.append("1");
      else
        throw new IllegalArgumentException("integer larger than 1 bit: " + i);
    return sb.toString();
  }

  public static Tuple<int[][],int[][]> exciseDiagonal(int[][] a) {
    int[][] d = new int[a.length][a.length == 0 ? 0 : a[0].length];
    int[][] r = new int[a.length][a.length == 0 ? 0 : a[0].length];
    for (int i = 0; i < d.length; i++)
      for (int j = 0; j < d[i].length; j++) {
        (i == j ? d : r)[i][j] = a[i][j];
      }
    return new Tuple<int[][],int[][]>(d,r);
  }

  public static Tuple<int[],Integer> jacobiIteration(int[][] a, int [] b, int maxIterations) {
    Tuple<int[][],int[][]> dr = exciseDiagonal(a);
    int [] x = new int[b.length];
    int [] ox = new int[b.length];
    for (int i = 0; i < x.length; i++)
      x[i] = Math.random() > .5 ? 1 : 0;
    int iterations = 0;
    while (iterations++ < maxIterations) {
      int diff = 0;
      for (int i = 0; i < x.length; i++)
        diff += Math.abs(x[i] - ox[i]);
      if (diff == 0)
        break;
      ox = x;
      x = Convo.apply(dr.snd, x);
      for (int i = 0; i < x.length; i++)
        x[i] = (b[i] ^ x[i]) / dr.fst[i][i];
    }
    return new Tuple<int[],Integer>(x, iterations);
  }

  public static void main(String[] argVector) {
    for (String s : argVector)
      for (int [] vector : convoUnapply(stringToTwoBitIntArray(s)))
        System.out.println(oneBitIntArrayToString(vector));
  }

}
